package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         73,
		Discription: "矩阵行列置0",
		Level:       2,
		Labels: map[string]int{
			"哈希表":  1,
			"空间复用": 1,
			"矩阵":   1,
		},
	})
}

// 先记录第0行和第0列是否需要全为0，然后用矩阵的第0行和第0列当哈希表
func SetZeroes(matrix [][]int) {
	isColumn0 := false
	isRow0 := false
	m := len(matrix)
	n := len(matrix[0])

	//先遍历第0行和第0列，看是否存在.，存在的话给个标记
	for i := 0; i < m; i++ {
		if matrix[i][0] == 0 {
			isRow0 = true
			break
		}
	}

	for j := 0; j < n; j++ {
		if matrix[0][j] == 0 {
			isColumn0 = true
			break
		}
	}

	//从第一行第一列开始遍历矩阵，如果元素为0，把对应的行和列置为0
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			if matrix[i][j] == 0 {
				matrix[i][0] = 0
				matrix[0][j] = 0
			}
		}
	}

	//从第一行第一列遍历矩阵，如果行或列为0，元素置为0
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			if matrix[i][0] == 0 || matrix[0][j] == 0 {
				matrix[i][j] = 0
			}
		}
	}

	//最后根据标记处理第0行和第0列
	if isColumn0 {
		for j := 0; j < n; j++ {
			matrix[0][j] = 0
		}
	}

	if isRow0 {
		for i := 0; i < m; i++ {
			matrix[i][0] = 0
		}
	}
}
